#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
typedef int ElemType;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode, *LinkList;

class SList
{
    private:
        LinkList head;
    public:
        SList();
        ~SList();
        void initList();
        void printList();
        void insertHead(int x);
        void insertTail(int x);
        //insert
        bool insertPNext(LinkList p, int x);
        bool insertPPre1(LinkList p, int x);
        bool insertPPre2(LinkList p, int x);
        bool insertAtPos(int pos, int x);
        //delete
        bool deleteP(LinkList p, ElemType &x);
        bool deleteAtPos(int pos, ElemType &x);
        //modify
        bool modifyP(LinkList p, int x);
        bool modifyAtPos(int pos, int x);
        //search
        bool searchAtPos(int pos, ElemType &x);
        bool searchAtElem(ElemType x, int &pos);
};

SList::SList()
{
    head = NULL;
    initList();
}

SList::~SList()
{
    while(head->next != NULL)
    {
        LinkList p = head->next;
        head->next = p->next;
        free(p);
    }
    free(head);
}

void SList::initList()
{
    //head is a pointer which points to the head node: 
    // head->|Node|->NULL
    head = (LNode*)malloc(sizeof(LNode));
    head->next = NULL;
}

void SList::printList()
{
    LinkList p = head->next;
    while(p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void SList::insertHead(ElemType x)
{
    LinkList s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    s->next = head->next;
    head->next = s;
}

void SList::insertTail(ElemType x)
{
    LinkList p = head;
    while(p->next != NULL)
    {
        p = p->next;
    }
    LinkList s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
}

bool SList::insertPNext(LinkList p, ElemType x)
{
    if (p == NULL)
    {
        return false;
    }
    LinkList s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return true;
}

bool SList::insertPPre1(LinkList p, ElemType x)
{
    if (p == NULL)
    {
        return false;
    }
    LinkList q = head;

    while(q->next != p)
    {
        q = q->next;
    }
    LinkList s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    s->next = p;
    q->next = s;
    return true;
}

bool SList::insertPPre2(LinkList p, ElemType x)
{
    if (p == NULL)
    {
        return false;
    }
    int temp = p->data;
    p->data = x;
    x = temp;
    return insertPNext(p, x);
}

bool SList::insertAtPos(int pos, ElemType x)
{
    LinkList p = head;
    int j = 0;
    while(p != NULL && j < pos - 1)
    {
        p = p->next;
        j++;
    }
    if(p == NULL)
    {
        return false;
    }
    LinkList s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return true;
}

bool SList::deleteP(LinkList p, ElemType &x)
{
    if(p == NULL)
    {
        return false;
    }
    LinkList q = head;
    while (q->next != p)
    {
        q = q->next;
    }
    x= p->data;
    q->next = p->next;
    p->next = NULL;
    free(p);
    return true;
}

bool SList::deleteAtPos(int pos, ElemType &x)
{
    LinkList p = head;
    int j = 0;
    while (p != NULL && j < pos-1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        return false;
    }
    LinkList q = p->next;
    x = q->data;
    p->next = q->next;
    q->next = NULL;
    free(q);
    return true;
}

bool SList::modifyP(LinkList p, ElemType x)
{
    if (p == NULL)
    {
        return false;
    }
    p->data = x;
    return true;
}

bool SList::modifyAtPos(int pos, ElemType x)
{
    LinkList p = head;
    int j=0;
    while (p != NULL && j < pos)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        return false;
    }
    p->data = x;
    return true;
}

bool SList::searchAtPos(int pos, ElemType &x)
{
    LinkList p = head;
    int j = 0;
    while (p != NULL && j < pos)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        return false;
    }
    x = p->data;
    return true;
}

bool SList::searchAtElem(ElemType x, int &pos)
{
    LinkList p = head;
    int j = 0;
    while (p != NULL)
    {
        j++;
        p = p->next;
        if (p != NULL && p->data == x)
        {
            pos = j;
            return true;
        }
    }
    return false;
}
void menu()
{
    printf("1: insertHead\n");
    printf("2: insertTail\n");
    printf("3: insertPNext\n");
    printf("4: insertPPre1\n");
    printf("5: insertPPre2\n");
    printf("6: insertAtPos\n");
    printf("7: deleteP\n");
    printf("8: deleteAtPos\n");
    printf("9: modifyP\n");
    printf("a: modifyAtPos\n");
    printf("s: searchAtPos\n");
    printf("d: searchAtElem\n");
    printf("p: printList\n");
}

void start(SList &slist, char c)
{
    ElemType x;
    int pos;
    
    switch (c)
    {
        case '1':
            printf("input x: ");
            scanf("%d", &x);
            slist.insertHead(x);
            break;
        case '2':
            printf("input x: ");
            scanf("%d", &x);
            slist.insertTail(x);
            break;
        case '3':
            printf("do nothing\n");
            break;
        case '4':
            printf("do nothing\n");
            break;
        case '5':
            printf("do nothing\n");
            break;
        case '6':
            printf("input: pos x: ");
            scanf("%d %d", &pos, &x);
            if (!slist.insertAtPos(pos, x))
            {
                printf("error\n");
                break;
            }   
            break;
        case '7':
            printf("do nothing\n");
            break;
        case '8':
            printf("input: pos:");
            scanf("%d", &pos);
            if (!slist.deleteAtPos(pos, x))
            {
                printf("error\n");
                break;
            }
            printf("delete x: %d\n", x);
            break;
        case '9':
            printf("do nothing\n");
            break;
        case 'a':
            printf("input: pos x: ");
            scanf("%d %d", &pos, &x);
            if (!slist.modifyAtPos(pos, x))
            {
                printf("error\n");
                break;
            }
            break;
        case 's':
            printf("input pos:");
            scanf("%d", &pos);
            if (!slist.searchAtPos(pos, x))
            {
                printf("error\n");
                break;
            }
            printf("x: %d\n", x);
            break;
        case 'd':
            printf("input x: ");
            scanf("%d", &x);
            if (!slist.searchAtElem(x, pos))
            {
                printf("error\n");
                break;
            }
            printf("pos: %d\n", pos);
            break;
        case 'p':
            slist.printList();
            printf("\n");
            break;
        default:
            menu();
            break;
    }
}
int main()
{
    SList slist;

    char c = ' ';
    while (c != 'q')
    {
        scanf("%c", &c);
        start(slist, c);
    }
    return 0;
}